在 Day 26 我們介紹了最小生成樹 (MST) 的概念，並提到兩個經典演算法: Kruskal 與 Prim。今天要深入探討 Kruskal 演算法，它以邊為導向，利用貪心法 (Greedy Algorithm) 與並查集 (Union-Find)，有效率地找出 MST

演算法原理

Kruskal 的核心思想是: 每次選擇當前最小的邊，只要不形成環，就把它加入生成樹，直到選出 $V-1$ 條邊。

這是一種貪心策略 (Greedy Strategy)，因為它每一步都選擇「目前最小代價」的選項，並且最終能證明得到的結果是最優解。

演算法步驟

• 將圖中所有邊依照權重大小排序。
• 初始化一個空集合，用來存放 MST 的邊。
• 依序取出最小邊，若這條邊不會與已選的邊形成環，則加入 MST。
• 重複直到選出 $V-1$ 條邊（V 為節點數）。

關鍵: 如何判斷是否成環?

這裡就需要 Union-Find (並查集):

• Find(x): 找到元素 x 所屬的集合代表（根節點）。
• Union(x, y): 將兩個集合合併。

如果一條邊 $(u, v)$ 的兩端節點已經在同一個集合，代表加入它會形成環，必須跳過。

Python 實作

Union-Find

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始化，每個節點的父節點指向自己
        self.rank = [0] * n           # 用 rank 優化，避免退化成鏈狀

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False  # 在同一集合，不能合併（會成環）
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True

Kruskal 演算法

def kruskal(V, edges):
    """
    V: 節點數
    edges: (u, v, w) 的邊清單
    """
    uf = UnionFind(V)
    mst = []
    edges.sort(key=lambda x: x[2])  # 按照權重排序

    for u, v, w in edges:
        if uf.union(u, v):  # 如果不成環，加入 MST
            mst.append((u, v, w))
            if len(mst) == V - 1:
                break
    return mst


# 測試
V = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst = kruskal(V, edges)
print("Kruskal MST:", mst)
# 輸出: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

複雜度分析

• 排序邊: $O(E \log E)$
• Union-Find 操作: $O(\alpha(V))$，近乎常數時間
• 總時間複雜度: $O(E \log E)$
  • E 為邊數，通常 $O(E \log V)$
• 空間複雜度: $O(V + E)$

Kruskal 適合 稀疏圖 (Sparse Graph)，因為邊排序的開銷不大。

Kruskal 的應用

• 網路設計
  • 例如建設光纖網路，確保所有城市連接，且總電纜長度最小。
• 聚類分析 (Clustering)
  • 先建立 MST，再刪去最大的幾條邊，可將圖分成多個子群。
• 地理與交通規劃
  • 設計最省成本的道路網，避免重複建設。

與 Prim 的比較

結語

Kruskal 演算法透過貪心策略與並查集，能快速構造出最小生成樹。它特別適合 邊數較少、稀疏圖 的情境，也是演算法課程與面試中必考的重點。